/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: GodK
 * Date: 2024-10-03
 * Time: 13:00
 */
public class Main {
    public static void sqort(int l,int r,int[] in){
        if(l >= r)return;
        int mid = (l + r) / 2;
        int i = l,left = l - 1,right = r + 1,key = in[mid];
        while (i < right){
            if(in[i] < key)swap(++left,i++,in);
            else if(in[i] == key)i++;
            else swap(i,--right,in);
        }
        //[l, left] [left +1,right-1] [rigth, r]
        sqort(l,left,in);
        sqort(right,r,in);
    }
    private static void swap(int i, int j, int[] in) {
        int tmp = in[i];
        in[i] = in[j];
        in[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {1,8,3,7,5,9,6};
        sqort(0,arr.length - 1,arr);
        for(int x : arr) System.out.println(x);
    }
}
